sup-extra HYSBZ-2809 dispatching 左偏树

Posted at 2019-01-19 ICPC 

HYSBZ-2809 dispatching 左偏树

题意就是要找一棵子树满足薪水和小于总预算的同时，节点数*子树根的领导力要最大。

解题的思路就是对树的每个节点都存储它的薪水和，如果超出了总预算就弹出最大的点。同时因为是DFS，所以回到高层之后就不用管底层的节点的状态了。同时为了能弹出最大的点，不能只存储薪水和，应当保留所有的薪水值，但是使用优先队列又不能快速合并两个优先队列，所以考虑使用可并堆左偏树。

至于什么是左偏树…… 就是左倾的树(迫真) 总之只要会用板子就行了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxl 1000006
using namespace std;
vector<int> tree[maxl];
int val[1000006],lead[1000006];
int lef[maxl],rig[maxl],dist[maxl],root[maxl];
int n,m;
long long res;
long long sum[maxl],coun[maxl];
int ltree_merge(int a,int b)//左偏树的合并操作
{
    if(a==0||b==0) return a+b;
    if(val[a]<val[b]) swap(a,b);
    rig[a]=ltree_merge(rig[a],b);
    root[rig[a]]=a;
    if(dist[rig[a]]>dist[lef[a]])
        swap(rig[a],lef[a]);
    if(rig[a]==0)
        dist[a]=0;
    else dist[a]=dist[rig[a]]+1;
    return a;
}
int ltree_pop(int k)//左偏树删除顶点的操作
{
    int l=lef[k],r=rig[k];
    root[l]=l;root[r]=r;
    lef[k]=rig[k]=dist[k]=0;
    return ltree_merge(l,r);
}
void dfs(int k)
{
    for(int i=0;i<tree[k].size();i++)
    {
        int v=tree[k][i];
        dfs(v);
        sum[k]+=sum[v];
        coun[k]+=coun[v];
        root[k]=root[v]=ltree_merge(root[k],root[v]);//将两个子树合成一个
    }
    while(sum[k]>m)//维护k点的左偏树
    {
        sum[k]-=val[root[k]];
        root[k]=ltree_pop(root[k]);
        coun[k]--;

    }
    res=max(res,coun[k]*lead[k]);
}
int main(void)
{

    while(~scanf("%d%d",&n,&m))
    {
        int fa;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&fa,&val[i],&lead[i]);
            tree[fa].push_back(i);//建树
            root[i]=i;
            coun[i]=1;
            sum[i]=val[i];
        }
        res=0;
        dfs(1);
        printf("%lld\n",res);
    }

	return 0;
}